package MiddlePractice;

public class Demo494 {
	
//	494. 目标和
//	给你一个整数数组 nums 和一个整数 target 。
//
//	向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：
//
//	例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。
//	返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
	
	public int findTargetSumWays(int[] nums, int target) {
		backTrack(nums, 0, target);
		return ans;
    }
	
	private int ans = 0;
	
	private void backTrack(int[] nums, int start, int reset) {
		if(start == nums.length) {
			if(reset == 0) {
				ans++;
				return;
			}
			return;
		}
		
		
		int newRet = reset + nums[start];
		backTrack(nums, start+1, newRet);
		
		newRet = reset - nums[start];
		backTrack(nums, start+1, newRet);
	}

	
}
